package com.stone;


import java.util.Stack;

public class Sort {
    public static void main(String[] args) {

        final int[] values = { 1, 3, 4, 5, 2, 8, 6, 7, 9, 0 };
        createBinaryTree(values);
        TreeNode binaryTree = build(values);
        System.out.println(binaryTree);
        inOrderTransvalWithIterate(binaryTree);
    }

    private static void createBinaryTree(int[] nums) {



        // return build(nums,0,nums.length - 1);
    }

    static TreeNode build(int[] nums) {

        //空值判断
        if (nums.length == 0 || nums == null) {
            System.out.println("为空");
        }

        //初始节点
        TreeNode root = new TreeNode();

        //遍历数组
        for (int i = 0; i < nums.length - 1; i++) {

            TreeNode node = new TreeNode();
            if (root.getVal() == null) {        //初始节点为空进行初始赋值
                root.setVal(nums[i]);
            } else if (root.getVal() > nums[i]) {
                node.setVal(nums[i]);           //父节点大于插入的节点父节点就放入左子节点
                root.setLeft(node);             //TODO  当大于插入的父节点值时会覆盖原本的左子节点，导致数据丢失问题，需完善

            } else if (root.getVal() < nums[i]) {
                node.setVal(nums[i]);           //父节点小于插入的节点父节点就放入右子节点
                node.setLeft(root);
                root = node;
            }
        }
        return root;
    }

    private static TreeNode build(int[] nums, int l, int r){
        if(l > r) return null;
        int mid = l + r >> 1;
        TreeNode root = new TreeNode(nums[mid]);

        if (root.getLeft()!= null){
            if (root.getVal() < root.getLeft().getVal()){
                int temp = root.getVal();
                root.setVal(root.getLeft().getVal());
                root.getLeft().setVal(temp);
            }
        }

        if (root.getRight()!= null){
            if (root.getVal() > root.getRight().getVal()){
                int temp = root.getVal();
                root.getRight().setVal(root.getVal());
                root.setVal(temp);
            }
        }

        if (root.getLeft()!= null && root.getRight()!= null){
            if (root.getRight().getVal() <root.getLeft().getVal()){
                int temp = root.getLeft().getVal();
                root.getLeft().setVal((root.getRight().getVal()));
                root.getRight().setVal(temp);
            }
        }


        root.setLeft( build(nums,l,mid - 1));
        root.setRight(build(nums,mid + 1,r));
        return root;
    }


    public static void inOrderTransvalWithIterate(TreeNode node) {
        //空值判断
        if (node == null) {
            System.out.println("为空");
            return;
        }

        while (true){
            if (node.getLeft()!=null){
                TreeNode left = node.getLeft();
            } else if (node.getRight()!=null){
                TreeNode right = node.getRight();
            }
        }

    }

    // 非递归实现
    // public static void inOrderTransvalWithIterate(int[] arr) {
    //
    //     for (int i = 0; i < arr.length - 1; i++) {
    //         for (int j = 0; j < arr.length - i - 1; j++) {
    //             if (arr[j] > arr[j + 1]) {
    //                 int k = arr[j];
    //                 arr[j] = arr[j + 1];
    //                 arr[j + 1] = k;
    //             }
    //         }
    //     }
    //
    //     for (int i = 0; i < arr.length; i++) {
    //         System.out.print(arr[i]);
    //     }
    // }
}
